package leetcode_day._2022._202201._0110;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/1/10 23:12
 * 累加数
 * 算法：回溯
 */
public class _10_306 {
    public static void main(String[] args) {
        System.out.println(new _10_306().isAdditiveNumber("199100199"));
    }

    public boolean isAdditiveNumber(String num) {
        if (num.length() < 3) return false;
        return dfs(num, 0, 0, 0, 0);
    }
    boolean dfs(String num, long pre, long sum, int idx, int cnt) {
        if (idx == num.length()) return cnt >= 3;
        long value = 0;
        for (int i = idx; i < num.length(); i++) {
            // 剪枝，如果数字以 0 开头，后面就都不能有数字
            if (i > idx && num.charAt(idx) == '0') break;
            value = value * 10 + num.charAt(i) - '0';
            if (cnt >= 2) {
                // 不够大
                if (value < sum) continue;
                // 太大了
                else if (value > sum) break;
            }
            if (dfs(num, value, value + pre, i + 1, cnt + 1)) return true;
        }
        return false;
    }

}
